package leetcode.pre100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
 * <p>
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 * <p>
 * 示例 1:
 * <p>
 * 输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出: [[1,5],[6,9]]
 * 示例 2:
 * <p>
 * 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出: [[1,2],[3,10],[12,16]]
 * 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/insert-interval
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @date 2020/4/5 16:53
 */
public class Code57_InsertRange_插入区间 {
    public static void main(String[] args) {
//        int[][] ints = {{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[][] ints = {{1, 3},{6,9}};
        int[] newInterval = {2, 5};
        int[][] merge = insert3(ints, newInterval);
        for (int[] ints1 : merge) {
            System.out.println(Arrays.toString(ints1));
        }
    }

    /**
     * 方式1：把newInterval复制到intervals中，
     * 调用{@link Code56_MergeRange_合并区间#merge(int[][])}
     * 空间O(interval)
     */
    public static int[][] insert1(int[][] intervals, int[] newInterval) {
        if (intervals == null || newInterval == null)
            return intervals == null ? new int[][]{newInterval} : intervals;
        if (newInterval.length == 0 || intervals.length == 0)
            return newInterval.length == 0 ? intervals : new int[][]{newInterval};
        int[][] inter = new int[intervals.length + 1][2];
        int i = 0;
        for (; i < inter.length; i++) {
            inter[i] = intervals[i];
        }
        inter[i] = newInterval;
        return new Code56_MergeRange_合并区间().merge(intervals);
    }

    /**
     * 方式2：在遍历的时候判断是否消耗了newInterval，
     * 比较intervals和newInterval谁小
     * 空间O(1)
     */
    public static int[][] insert2(int[][] intervals, int[] newInterval) {
        if (intervals == null || newInterval == null)
            return intervals == null ? new int[][]{newInterval} : intervals;
        if (newInterval.length == 0 || intervals.length == 0)
            return newInterval.length == 0 ? intervals : new int[][]{newInterval};
        //intervals已经有序
        //newInterval是否已经被使用
        boolean consumed = false;
        LinkedList<int[]> list = new LinkedList<>();
        if (intervals[0][0] < newInterval[0]) {
            list.add(new int[]{intervals[0][0], intervals[0][1]});
        } else {
            list.add(new int[]{newInterval[0], newInterval[1]});
            consumed = true;
        }
        int i = consumed ? 0 : 1;
        for (; i < intervals.length; ) {
            //从intervals数组中拿出来比较
            if (consumed) {
                doMerge(list, intervals[i]);
                i++;
            } else {
                boolean newMin = newInterval[0] < intervals[i][0];
                //newInterval小，被合并
                if (newMin) {
                    doMerge(list, newInterval);
                    consumed = true;
                } else {
                    doMerge(list, intervals[i]);
                    i++;
                }
            }

        }
        //考虑可能interval遍历完，newInterval还没有consume
        if (!consumed) {
            doMerge(list, newInterval);
        }
        return list.toArray(new int[0][0]);
    }

    /**
     * 合并区间：把interval合并到list上
     */
    private static void doMerge(LinkedList<int[]> list, int[] interval) {
        if (interval[0] <= list.getLast()[1]) {
            list.getLast()[1] = Math.max(list.getLast()[1], interval[1]);
        } else {
            list.add(new int[]{interval[0], interval[1]});
        }
    }

    /**
     * 方式3：使用堆，把interval和newInterval放入到一个小跟堆，然后合并
     */
    public static int[][] insert3(int[][] intervals, int[] newInterval) {
        if (intervals == null || newInterval == null)
            return intervals == null ? new int[][]{newInterval} : intervals;
        if (newInterval.length == 0 || intervals.length == 0)
            return newInterval.length == 0 ? intervals : new int[][]{newInterval};
        Queue<int[]> minQ = new PriorityQueue<>((int1,int2) -> int1[0] - int2[0]);
        for (int[] interval : intervals) {
            minQ.offer(interval);
        }
        minQ.offer(newInterval);
        LinkedList<int[]> list = new LinkedList<>();
        list.add(minQ.poll());
        while (!minQ.isEmpty()){
            int[] poll = minQ.poll();
            if(list.getLast()[1] >= poll[0]){
                list.getLast()[1] = Math.max(list.getLast()[1],poll[1]);
            }else {
                list.add(poll);
            }
        }
        return list.toArray(new int[0][0]);
    }
}
